\section{LRU}

\subsection{Descripción}

El algoritmo Least Recently Used (LRU) descarta primero los elementos menos usados recientemente. El algoritmo lleva el seguimiento de lo que se va usando, lo que resulta caro si se quiere hacer con precisión. La implementación de esta técnica requiere llevar la cuenta de la edad de cada elemento de caché y buscar el menos usado en base a ella. En una implementación como esa, cada vez que se usa un elemento, la edad de todos las demás elementos cambia.

\subsection{Implementación}

\subsubsection{LRU Buffer Frame}

\begin{lstlisting}
package ubadb.core.components.bufferManager.bufferPool.replacementStrategies.lru;

import java.util.Date;

import ubadb.core.common.Page;
import ubadb.core.components.bufferManager.bufferPool.BufferFrame;
import ubadb.core.exceptions.BufferFrameException;

public class LRUBufferFrame extends BufferFrame 
{                
		private Date referencedDate;
	
        public LRUBufferFrame(Page page) {
                super(page);     
                referencedDate = new Date();
        }
        
        public Date getReferencedDate()
    	{
    		return referencedDate;
    	}
        
        public void pin(){
        	super.pin();
        	referencedDate = new Date();
        }
        
        public void unpin() throws BufferFrameException{
        	super.unpin();
        	referencedDate = new Date();
        }


}
\end{lstlisting}

\subsubsection{LRU Buffer Frame Strategy}

\begin{lstlisting}
package ubadb.core.components.bufferManager.bufferPool.replacementStrategies.lru;

import java.util.Collection;
import java.util.Date;

import ubadb.core.common.Page;
import ubadb.core.components.bufferManager.bufferPool.BufferFrame;
import ubadb.core.components.bufferManager.bufferPool.
	replacementStrategies.PageReplacementStrategy;
import ubadb.core.exceptions.PageReplacementStrategyException;

public class LRUReplacementStrategy implements PageReplacementStrategy
{       
    public BufferFrame findVictim(Collection<BufferFrame> bufferFrames) throws PageReplacementStrategyException
    {               
    	LRUBufferFrame victim = null;
		Date oldestReplaceablePageDate = null;
		
		for(BufferFrame bufferFrame : bufferFrames)
		{
			LRUBufferFrame lruBufferFrame = (LRUBufferFrame) bufferFrame; //safe cast as we know all frames are of this type
			if(lruBufferFrame.canBeReplaced() && (oldestReplaceablePageDate==null || 
				lruBufferFrame.getReferencedDate().
					before(oldestReplaceablePageDate)))
			{
				victim = lruBufferFrame;
				oldestReplaceablePageDate = lruBufferFrame.getReferencedDate();
			}
		}
		
		if(victim == null)
			throw new PageReplacementStrategyException("No page can be removed from pool");
		else
			return victim;
    }
    
    public BufferFrame createNewFrame(Page page) 
    {
    	return new LRUBufferFrame(page);                     
    }
    
    public String toString() {
    	return "LRU Replacement Strategy";
    }
}
\end{lstlisting}
